// https://www.lintcode.com/problem/3sum/my-submissions

class Solution {
public:
    /**
     * @param numbers: Give an array numbers of n integer
     * @return: Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int>> threeSum(vector<int> &numbers) {
        vector<vector<int>> result;
        sort(numbers.begin(), numbers.end()); //排序为方便处理重复的
        for (int i = 0; i < numbers.size(); ++i)
        {
            if (i && numbers[i] == numbers[i - 1]) continue;
            int target = -numbers[i];
            int low = i + 1;
            int high = numbers.size() - 1;
            while (low < high)
            {
                int tmp = numbers[low] + numbers[high];
                if (tmp == target)
                {
                    vector<int> vec = {numbers[i], numbers[low], numbers[high]};
                    result.push_back(vec);
                    low++;
                    high--;
                    while (low < high && nums[low] == nums[low - 1]) low++;
                    while (low < high && nums[high] == nums[high + 1]) high--;
                }
                else if (tmp > target) high--;
                else low++;
            }
        }
        return result;
    }
};